package com.wtgroup.demo.mianshi.算法.链表;

import com.wtgroup.demo.common.bean.LinkNode;

/**
 * 类似荷兰国旗问题
 *
 * @author nisus
 * @version 0.1
 * @since 2023/5/2 15:15
 */
public class Q_链表大中小划分 {

    // 放到数组中，荷兰国旗方式划分
    static class S1 {

        LinkNode doit(LinkNode head, int pivot) {
            if (head == null) {
                return head;
            }
            int len = 0;
            LinkNode curr = head;
            for (; curr != null; curr = curr.next) {
                len++;
            }

            LinkNode[] arr = new LinkNode[len];
            curr = head;
            for (int i = 0; i < arr.length; i++, curr = curr.next) {
                arr[i] = curr;
            }

            // 三分
            threePartify(arr, pivot);

            return null;
        }

        private void threePartify(LinkNode[] arr, int pivot) {
            // 荷兰国旗方式划分三区域
        }


    }

    /**
     * O(1) 空间
     * 准备小中大三个空链
     */
    static class S2 {

    }

}
